1. Field of the Invention
The present invention is directed generally to methods of performing social searches and web searches involving the use of data from social networks and social graphs.
2. Description of the Related Art
The term “social graph” is familiar to those of ordinary skill in the art and was coined by scientists working in social areas of graph theory. The term “social graph” has been described as a global mapping of everybody and how they are related to one another.
Some online service providers collect, generate, and store information about users in a structure referred to as a social graph. The social graph may be stored in one or more data structures. In some implementations, the social graph is stored in a database. As is apparent to those of ordinary skill in the art, a graph includes nodes connected together by links. While implementations of a social graph may vary, generally speaking, in a social graph, users (which may include entities) are represented by nodes and relationships between the nodes are represented by links. For example, a first user may identify a second user as a “friend.” In this example, the first user may be represented by a first node, the second user may be represented by a second node, and the “friend” relationship may be represented by a link (e.g., having a type “friend”). The link may be one-way indicating the second user is a “follower” of the first user, but not indicating the first user is also “following” or “followed by” the second user. If the second user has indicated the first user is a “friend,” the link between the first and second users may indicate a two-way (or mutual) “friend” relationship exists between the first and second nodes. A link may exist even if the first and second users are unfamiliar with each other. Furthermore, a link may exist if the first user is familiar with the second user, but the second user is not familiar with the first user. In another example, a link may exist if the second user is familiar with the first user, but the first user is not familiar with the second user. A link may identify other types of relationships (other than a “friend” relationship). For example, a link may identify a “contact” relationship, an “acquaintance” relationship, a business relationship, a work relationship, and the like.
FIG. 1 provides an illustration of a social graph 10 including the Users A-J. The social graph 10 may be characterized as being associated with the User A (or as being User A's social graph). In the social graph 10, the User A has a mutual relationship with the User B and a one-way relationship with each of the Users C-E. Thus, in this example, the Users A and B may be “following” each other. Further, the User A may be “following” each of the Users C-E, while none of the Users C-E are following the User A. Therefore, the User A may be classified as a “follower” of the Users B-E.
As is also apparent to those of ordinary skill in the art, methods exist for traversing and searching a social graph, such as the social graph 10.
Each user may be characterized as having a social graph. The social graph 10 illustrated in FIG. 1 is associated with the User A and shows connections between the User A and the Users B-J. However, depending upon the implementation details, the social graphs of at least a portion of the users may be connected such that they form a single social graph. A social graph may be characterized as storing information about a user on a “social network.”
Within the social graph, a particular user (represented by a node) may be connected directly to one or more nodes. Such a direct connection is often referred to as a first degree connection. In FIG. 1, the Users B-E have first degree connections with the User A.
A second degree connection includes nodes connected directly to the nodes of the first degree connection (other than the node representing the particular user). In FIG. 1, the Users F, H, and I have second degree connections with the User A. Further, because a mutual connection exists between the nodes representing the Users C and D, each of the Users C and D also has a second degree connection with the User A.
A third degree connection includes nodes connected directly to the nodes of the second degree connection (other than the nodes of the first degree connection), and so forth. In FIG. 1, the User G has a third degree connection with the User A.
Further, nodes may be connected to the social graph 10 from other social graphs. For example, a node representing the User J is connected to the node representing the User C via a one-way relationship indicating the User J is following the User C. Thus, the node representing the User J is not actually part of the social graph 10 but is connected thereto.
Social search or a social search engine is a type of web search that takes into account information stored in at least a portion of a social graph associated with the user who is running a search query. The information stored in the social graph may be used by the social search to determine relevance of the results obtained by the web search.
There are currently a number of companies that offer products that attempt to provide social search. However, none of the currently available technologies provide truly relevant search results. Further, many of the currently available technologies are easily manipulated.
As is apparent to those of ordinary skill in the art, some online service providers allow users to indicate preferences or opinions related to items of interest (e.g., goods, services, locations, etc.). For example, some service providers allow users to indicate they “like” a particular item of interest. If a user has indicated the user “likes” a particular item of interest, the user has indicated a positive opinion related to that item, which may be considered a “vote” for the item. Thus, by “liking” an item of interest, the user has “voted up” that item.
A popular approach to social search is to use at least a portion of a social graph related to a particular user executing the search query to identify a portion of the nodes of the social graph. For example, the social search may identify nodes representing the user's friends, the user's contacts, and/or anyone. Then, the social search determines how many “votes” each of the search results (e.g., websites, content, files, and/or data) has obtained from the nodes identified. The number of votes received from the nodes identified may be used to select which search results to display or determine how the search results are to be displayed (e.g., used to determine a sort order) to the user. This method has some problems. For example, because it is difficult to determine whether a particular node (e.g., a node representing a “friend”) has the same tastes and preferences as the user executing the social search, the method may not return particularly relevant search results or order them a particularly useful way. This method also does not help determine whether the particular node is legitimate, has expertise in the area(s) in which the node is voting, etc. Thus, using the number of votes received from the nodes identified to select or display the search results may not yield desirable search results for the user executing the social search.
Additionally, current social search technologies are prone to types of abuse in which the search results are manipulated. A spammer is typically a person or other type of entity that sends unwanted messages, emails, friend requests, votes, etc. (often in bulk) to other users. However, the term “spammer” may also describe person or other type of entity that manipulates or takes advantage of a social networking service and/or web search service in an inappropriate, abusive, and/or illegal manner. Often, these activities are in violation of a user agreement between the spammer and the social networking service.
An example of a type of inappropriate activity sometimes engaged in by a spammer includes manipulating a user's search results obtained via a social search. A spammer may manipulate some types of social search by executing a program (typically referred to as a robot) that automatically adds nodes (e.g., representing users) to the spammer's social graph linked to the spammer as “friends.” The spammer may then “vote up” search results that benefit the spammer. By “voting up” selected search results, the spammer manipulates the search results for all of the spammer's “friends” in the social graph. Some of these “friends” may include legitimate users who added the spammer to their social graphs (e.g., via a friends list) simply to increase their number of friends (referred to as a friends count).
Thus, social search technologies available today are largely ineffective and provide irrelevant results that can easily be manipulated. Therefore, a need exists for methods of implementing a social search that provide personalized and/or relevant search results to a user. Methods that are difficult to manipulate would be particularly desirable. The present application provides these and other advantages as will be apparent from the following detailed description and accompanying figures.